package branch_and_price;

import java.util.ArrayList;
import java.util.Random;

// 贪心算法
public class Greedy {
    // 访问点个数
    private int n;
    private Data data;
    private ArrayList<Integer> nodes;

    public Greedy(Data d){
        this.data = d;
        n = d.getN();
    }

    // 使用贪心算法计算一个初始解
    public ArrayList<Integer> solve(){
        nodes = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            nodes.add(i);
        }
        ArrayList<Integer> route = new ArrayList<>();
        route.add(0); // 从0出发
        Random random = new Random();
        // 使用随机的方法，生成TSP路线
        while (true){
            if (nodes.isEmpty()){
                break;
            }
            int index = random.nextInt(nodes.size());
            route.add(nodes.remove(index));
        }
        route.add(0); // 回到 0
        return route;
    }
}